#include <algorithm>
#include <string>
#include <unordered_set>
#include <vector>

class Solution
{
 public:
  vector<string> Permutation(string str)
  {
    vector<string> result;
    if (str.empty()) return result;

    per(str, 0, result);

    // 此时得到的result中排列并不是字典顺序，可以单独再排序
    // 排序，以便之后产生字典序的全排列(这里是产生序列之后再排序，通过改进算法可以实现按字典序push)
    std::sort(result.begin(), result.end());

    return result;
  }

 private:
  void per(string str, int begin, vector<string>& result)
  {
    if (begin == str.size() - 1)  // 递归结束条件，索引已经指向str最后一个元素时
    {
      // 如果result中不存在str,才添加；避免aa和aa重复添加的情况
      result.push_back(str);
    }
    else
    {
      unordered_set<char> record;  // 记录出现过的字符,临时变量

      // 第一次循环i与begin相等，相当于第一个位置自身交换，关键在于之后的循环
      // 之后i != begin，则会交换两个不同位置上的字符，直到begin==str.size()-1，进行输出
      for (int i = begin; i < str.size(); ++i)  // 产生排列的多个分支
      {
        if (record.find(str[i]) == record.end())  // 只和没交换过的交换
        {
          record.insert(str[i]);
          swap(str[begin],
               str[i]);  // 与后面元素交换，以产生不同字符开头的排列(把后面元素和第0个元素交换）
          per(str, begin + 1, result);  // 比如以str[begin]开头，固定str[begin]剩下的作全排列
          swap(str[begin],
               str[i]);  // 复位，用以恢复之前字符串顺序，达到第一位依次跟其他位交换的目的
        }
      }
    }
  }

  void swap(char& fir, char& sec)
  {
    char temp = fir;
    fir = sec;
    sec = temp;
  }
};

/*全排列
#include <stdio>

void printArray(int A[], int n)
{
  int i;
  for(i=0; i<n; i++)
  {
    printf("%d", A[i]);
  }
  printf("\n");
}

// 交换值
void swap(int a[], int i, int j)
{
  int temp = A[i];
  A[i] = A[j];
  A[j]=temp;
}

void perm(int A[], int p, int q)
{
  if(p==q) // 递归出口
  {
    printArray(A,q-1);
  }
  else
  {
    int i;
    for(i=p; i<=q;i++)
    {
      swap(A, p,i);
      perm(A,p+1,q);
      swap(A,p,i);
    }
  }
}

int main()
{
  int A[3] = {1,2,3};
  perm(A, 0, 2);
}*/